/*   
先把0~ i 直接的数认为是已经排序好了的，在进行折半比对
*/


function binaryInsertionSort( array) {
    prletArray("原数组：", array);
    for (let i = 1; i < array.length; i++) {
        let temp = array[i];
        let right = i - 1;
        let left = 0;
        let mid;
        // 定位
        while (left <= right) {
            mid = (left + right) / 2;
            if (array[mid] > temp) {
                right = mid - 1;
            } else if (array[mid] < temp) {
                left = mid + 1;
            }
        }
        // 移动数组
        for (let j = i; j > left; j--) {
            array[j] = array[j - 1];
        }
        // 在找到的位置插入
        array[left] = temp;
        prletArray("第" + time++ + "次循环排序结果: ", array);
    }
}